package org.example.myleet.p581;

/**
 * 单调栈
 * 思路：
 * 需要排序的连续子数组的左边界是左边开始单调递增的最大数字，右边界是右边开始单调递减的最小数字
 * 确定左边界，将元素逐个压入栈中，为了保持栈的单调性，当遇到大于栈顶的数之后，不再继续压入栈，而是不断弹出更大的栈顶，直到遍历完所有元素
 * 右边界同理，只是反方向
 * 时间复杂度：O(2*n)，正反方向各一次遍历
 */
public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        //最简单的数组模拟栈
        int len = 0;
        int[] stack = new int[nums.length];
        //确定左边界
        stack[len++] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            if (stack[len - 1] > nums[i]) {
                //遇到比栈顶大的数，后面不再压入，而是不断将栈顶更大的数弹出
                while (len > 0 && stack[len - 1] > nums[i]) {
                    --len;
                }
                for (int j = i + 1; j < nums.length; ++j) {
                    if (len > 0) {
                        //数组剩下的元素如果比栈顶大，栈顶也要弹出，保证左边界的左边是单调递增的
                        while (len > 0 && stack[len - 1] > nums[j]) {
                            --len;
                        }
                    } else {
                        break;
                    }
                }
                break;
            } else {
                stack[len++] = nums[i];
            }
        }
        int l = len - 1;
        //确定右边界
        len = 0;
        stack[len++] = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; --i) {
            if (stack[len - 1] < nums[i]) {
                //遇到比栈顶小的数，后面不再压入，而是不断将栈顶更小的数弹出
                while (len > 0 && stack[len - 1] < nums[i]) {
                    --len;
                }
                for (int j = i - 1; j >= 0; --j) {
                    if (len > 0) {
                        //数组剩下的元素如果比栈顶小，栈顶也要弹出，保证右边界的右边是单调递增的（向左方向看的时候是保持递减）
                        while (len > 0 && stack[len - 1] < nums[j]) {
                            --len;
                        }
                    } else {
                        break;
                    }
                }
                break;
            } else {
                stack[len++] = nums[i];
            }
        }
        int r = nums.length - 1 - len;
        if (l >= r) {
            return 0;
        }
        return r - l;
    }
}
